package com.example.algorithm.huawei_rongyao_29;
import java.util.Scanner;


// 求最小公倍数
/**
 * 要计算两个正整数 A 和 B 的最小公倍数（LCM），可以利用它们的最大公约数（GCD）的性质。
 * LCM(A, B) = A * B / GCD(A, B)。
 * 因此，我们只需要计算出 A 和 B 的最大公约数，然后用它们的乘积除以最大公约数即可得到最小公倍数。
 *
 * 求最大公约数，可以使用，辗转相除法，也就欧几里得算法
 * 假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
 * 1997 ÷ 615 = 3 (余 152)
 * 615 ÷ 152 = 4(余7)
 * 152 ÷ 7 = 21(余5)
 * 7 ÷ 5 = 1 (余2)
 * 5 ÷ 2 = 2 (余1)
 * 2 ÷ 1 = 2 (余0)
 * 至此，最大公约数为1
 *
 * 下面程序，经过试验测试，正确。
 * */
public class Q11_LeastCommonMultiple {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int lcm = calculateLCM(a, b);
        System.out.println(lcm);
        scanner.close();
    }

    public static int calculateLCM(int a, int b) {
        // 计算最大公约数
        int gcd = calculateGCD(a, b);
        // 计算最小公倍数
        return a * b / gcd;
    }

    public static int calculateGCD(int a, int b) {
        // 使用欧几里得算法求解最大公约数
        // b等于0表示，除法能整除，一旦除法能整除，就说明找到了最大公约数
        while (b != 0) {
            int temp = b;
            b = a % b; // a对b取模。余数被b接收
            a = temp;
        }
        return a;
    }
}

